第十天 CPU Scheduling--下

昨天講完Multiple-Processor Scheduling，今天來說說Real-Time CPU Scheduling。

Real-Time CPU Scheduling(即時應用排程)：
Real-Time system分為兩種：

1. soft real-time system：會盡量完成工作，但不保證
2. hard real-time system：所有工作要在時間內完成

而影響real-time system的主要因素為latency：

• interrupt latency：中斷造成得時間延遲
• dispatch latency：process轉換耗費的時間、決定哪個process用CPU

在real-time system中，根據優先權做排程(priority-based scheduling)是很重要的(只在soft real-time有保證)。假設process的執行時間是t、deadline是d、週期時間是p，如果t < d < p，check的頻率就是1/p。

而我們之前提到，一個作業系統中有很多個作業系統(guest OS)，這是在虛擬化的環境下執行。如果每個guest OS做自己的排程，就會有下列幾個問題：

• 不知道自己沒有能力控制CPU
• Response time沒有自己單一控制CPU來得好
• 不同的作業系統，處理時間不一樣

而在real-time scheduling中運用的演算法有：

1. Rate Monotonic Scheduling：
   是最常用的演算法，依據頻率高低決定優先權，週期短(頻率高)有高優先權，週期長(頻率低)較低優先權。以下為例題跟運算：
   

   但這個演算法有時會把deadline給miss掉，所以有了下一個演算法來彌補

2. Earliest Deadline First Scheduling：
   依據誰的deadline先到，誰的優先權就越高。以下有範例即運算：
   

3. Proportional Share Scheduling：
   這種演算法比較注重公平性，假設T是CPU時間、N是application要分享CPU的時間(N < T)，這樣每個application都收到N / T時間，但事前需要把資源比例分配好。

那上面那麼多演算法，我們要怎們選擇呢？這時我們可以用以下幾種評估方式：

1. Deterministic modeling：
   是以分析的方式，選擇哪種演算法適合。但是我們沒有那麼多時間，可以用運算waiting time的時間做分析。
2. Queueing modeling：
   已排隊的情形來決定，他有一個重要的公式—Little’s Law，以下是他的說明：
   
   n是平均queue的長度
   W是在queue平均waiting time
   λ是平均進到queue的速度
3. Simulations：
   在模擬環境中執行看結果，以下有舉例：
   
4. Implementation：
   實作出來，但是會耗費金錢且有高風險，不知道做出來是不是真的是最好的。

以上我們就講完CPU Scheduling啦！